Správu fyzickej pamäte má na starosti alokátor fyzickej pamäte implementovaný v kernel/kalloc.c; ide predovšetkým o dvojicu funkcií kalloc() a kfree(). Na správu fyzickej pamäte slúži riadiaca štruktúra alokátora kmem:
|
1 2 3 4 |
struct { struct spinlock lock; struct run *freelist; } kmem; |
Položka lock slúži na zabezpečenie prístupu k zoznamu voľných blokov freelist. V položke freelist je uchovávaná adresa začiatku zoznamu voľných rámcov fyzickej pamäte. V prípade, že je rámec voľný, adresa nasledovného voľného bloku sa uchováva na začiatku samotného bloku. Ak blok voľný nie je, ale je alokovaný, v zozname voľných blokov sa nenachádza. Inicializácia alokátora prebieha v dvojriadkovej funkcii kinit():
|
1 2 3 4 5 6 |
void kinit() { initlock(&kmem.lock, "kmem"); freerange(end, (void*)PHYSTOP); } |
Prvý riadok inicializuje zámok, na druhom sa volá špeciálna funkcia uvoľnenia rozsahu fyzickej pamäte: prvý argument je začiatok oblasti, druhý koniec. Funkcia prechádza celý rozsah fyzickej pamäte a pre každú adresu, ktorá je začiatkom stránky, volá funkciu free(), čím sa daná stránka dostane do zoznamu voľnej pamäte.
Samotné funkcie kalloc() a kfree() sú triviálne: prvá odoberá zo zoznamu voľných blokov, druhá do neho pridáva. Manipulácia so zoznamom sa robí pri zamknutom zámku. Okrem toho kfree() kontroluje vstupnú adresu, ktorá musí byť zarovnaná na stránku a z rozsahu platných fyzických adries. Obe funkcie vypĺňajú alokovanú/uvoľnenú stránku zvolenou konštantou, aby sa ľahšie hľadali programátorské chyby.
Z uvedeného vidno, že okrem zoznamu voľných rámcov nemá alokátor žiadnu informáciu o stave rámcov. Na úspešné dokončenie COW potrebujeme nejaký mechanizmus, pomocou ktorého budeme vedieť, ktorý rámec má koľko mapovaní. Je zrejmé, že rámce, ktoré sú voľné, budú mať 0 mapovaní (voľný rámec nemôže byť predsa pripojený do žiadneho virtuálneho adresného priestoru). Aby sme vedeli sledovať počet mapovaní, rozšírime štruktúru kmem o ďalšiu položku:
|
1 2 3 4 5 |
struct { struct spinlock lock; struct run *freelist; uint64 *cntref; } kmem; |
cntref bude pole, pre ktoré bude platiť, že každý prvok zodpovedá práve jednému rámcu pamäte. Tí vnímavejší si neskôr môžu všimnúť, že pre niektoré rámce fyzickej pamäte v poli nebudú jestvovať záznamy, a pre niektoré rámce fyzickej pamäte sa zasa nikdy ich stav v poli nebude meniť. Ale to sú už raz dané čary programovania…
Je zrejmé, že pole referencií potrebujeme nejako inicializovať. Na tento účel sa najvhodnejšou javí funkcia incializácie alokátora, kinit().
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void kinit() { int frames = 0; uint64 addr = PGROUNDUP((uint64)end); kmem.cntref = (uint64*)addr; while(addr < PHYSTOP){ kmem.cntref[PA2IND(addr)] = 1; addr += PGSIZE; frames++; } initlock(&kmem.lock, "kmem"); freerange(kmem.cntref+frames, (void*)PHYSTOP); } |
Pri postupnej inicializácií pomocou premennej frames počítame počet dostupných rámcov. Začiatok poľa kmem.cntref určíme za symbolom end jadra xv6. Autori xv6 zaviedli tento symbol preto, aby bolo jasné, na akej fyzickej adrese končia údaje a kód jadra. Za touto adresou je fyzická pamäť voľná. Preto si môžeme dovoliť zaokrúhliť (ale ono by to malo fungovať aj bez zaokrúhlenia – experimentálne to overte) hodnotu prvého bajtu voľnej fyzickej pamäte end nahor na celé stránky. Potom budeme postupne prechádzať celú voľnú fyzickú pamäť až po hornú hranicu PHYSTOP (xv6 dokáže pracovať iba s fyzickou pamäťou do veľkosti PHYSTOP). Pre každú stránku pamäte nastavíme v poli cntref počet referencií na 1. Prečo na 1, keď sa má jednať o voľné bloky pamäte? Pretože sme programátori… Keď sa pozrieme na posledný riadok funkcie kinit(), voláme funkciu freerange(). Ako sme už vysvetlili vyššie, v tejto funkcii sa znovu prechádza celý interval voľnej pamäte, a na každý rámec sa volá funkcia free(). Ešte sme úpravu tejto funkcie síce nespomínali, ale prezradíme toľko, že vo funkcii free() sa bude znižovať počet referencií na rámec. Akonáhle klesne na 0, rámec sa pridá do zoznamu voľných stránok fyzickej pamäte.
Niekto si možno všimne, že pri prístupe do poľa cntref máme k dispozícií fyzickú adresu, nie index. Nejakým spôsobom však musíme previesť fyzickú adresu na index do poľa, inak by sme nevedeli pole rozumne použiť. Na to nám poslúži makro PA2IND():
|
1 |
#define PA2IND(pa) (((uint64)pa - PGROUNDUP((uint64)end))/PGSIZE) |
Vstupom makra je fyzická adresa pa. Ak od tejto adresy odpočítame začiatočnú adresu oblasti, pre ktorú chceme evidovať referencie, a takto získanú hodnotu podelíme veľkosťou stránky, dostaneme číslo stránky, pre ktorú chceme zistiť/nastaviť počet referencií (toto vypočítané číslo stránky je priamo indexom do poľa cntref). Upozornenie: takto vypočítané číslo stránky nemá nič spoločné s PPN v PTE záznamoch! Pri sledovaní referencií nás totiž nezaujíma celá fyzická pamäť (od adresy 0), ale iba časť pamäte od adresy PGROUNDUP(end). Nikdy totiž nebudeme uvoľňovať fyzickú pamäť kódu a údajov jadra! Preto fyzická pamäť v intervale ⟨0; PGROUNDUP(end)) nie je predmetom sledovania referencií, a žiaden index poľa cntref nie je s touto pamäťou spojený.
Pre názornosť prikladáme veľmi zjednodušenú schému fyzickej pamäte, na ktorej vidno rozdelenie na rámce, hodnoty a premenné použité pre správu referencií:
Napísať funkcie na zvyšovanie či znižovanie počtu referencií je jednoduché, keď už máme k dispozícií pole, ktoré bude sledovať tieto počty pre jednotlivé rámce voľnej fyzickej pamäte a makro, pomocou ktorého získame index do poľa na základe fyzickej adresy.
|
1 2 3 4 5 6 7 8 |
def dec_ref(pa): get_lock(kmem.lock) if cntref[pa] is 0: panic("dec_ref: cntref zero") cntref[pa] -= 1 ret = cntref[pa] release_lock(kmem.lock) return ret |
Funkcia dec_ref() najprv získa zámok pre prácu s fyzickou pamäťou; zámok môže byť užitočný, pokiaľ by viaceré procesory súčasne začali vykonávať kód dec_ref()/inc_ref() pre tú istú fyzickú adresu. Ak by nebol použitý riadený prístup po jednom na modifikáciu prvku poľa cntref[pa], súčasná modifikácia viacerých cpu jedného pamäťového miesta by mohla viesť ku nekonzistencii počtu referencií pre fyzickú stránku pa.
Po získaní zámku je nutné skontrolovať správnosť volania funkcie dec_ref(). Táto funkcia nesmie byť vyvolaná pre stránku, ktorá má počet referencií 0, t. j. pre nepoužitú (voľnú) stránku. Keby k takému volaniu prišlo, jedná sa o chybu prográtora jadra, a preto o takejto situácii treba ihneď informovať – napríklad pomocou ukončenia behu OS spolu s výpisom, kde ku chybe prišlo.
Po kontrole je možné znížiť počet refrencií na stránku o 1, uložiť návratovú hodnotu (tou je aktuálny počet referencií), uvoľniť zámok a vrátiť počet referencií na stránku. Vrátenú hodnotu vhodne využijeme vo funkcii kfree().
|
1 2 3 4 |
def inc_ref(pa): get_lock(kmem.lock) cntref[pa] += 1 release_lock(kmem.lock) |
Funkcia inc_ref() je jednoduchšia: po získaní zámku iba zvýši hodnotu počítadla referencií pre fyzickú stránku pa. Treba si uvedomiť, že takto napísaná funkcia v sebe obsahuje minimálne jednu nedotiahnutú vec – a tou je pretečenie počítadla referencií. Podobne ako v prípade funkcie dec_ref() kontrolujeme validitu volania vzhľadom na hodnotu počítadla, tak aj v tejto funkcii treba doplniť kontrolu validity volania vzhľadom na maximálny možný počet referencií. Táto hodnota ovšem závisí od typu, ktorý používame na počítanie. V tomto návode pole cntref obsahuje prvky typu uint64, takže podľa toho treba zvážiť implementáciu testu. Pravdaže, najlepšie by bolo test napísať dostatočne univerzálne na to, aby sa pri preklade vždy určila správna maximálna hodnota podľa použitého typu prvkov poľa cntref.
kalloc() a kfree()Vo funkcii kfree() je použitie dec_ref() triviálne:
|
1 2 3 |
// If ref count is not zero, silently continue. if(dec_ref(pa) != 0) return; |
Tieto dva riadky kódu treba pridať do tela funkcie pred volanie funkcie, ktorá premazáva obsah stránky! Ako funguje uvoľňovanie stránky? Najprv sa skontroluje platnosť argumentu (fyzická adresa musí byť zarovnaná na stránku, musí byť v správnom rozsahu fyzických adries), potom sa zavolá dec_ref(). Ak je aj po znížení počtu referencií hodnota počítadla pre stránku väčšia než nula, znamená to, že ešte jestvuje mapovanie tejto stránky do nejakého (resp. viacerých) virtuálneho priestoru. Preto funkcia kfree() nebude pokračovať vo fyzickom uvoľnení rámca a jeho zaradení do zoznamu voľných, ale skončí beh. Nejedná sa o chybu, presne takéto správanie očakávame.
Všimnime si, že volanie dec_ref() je vykonané ešte predtým, než kfree() zamkne zámok. Môže prísť ku chybe a nekonzistencii údajov? Nemalo by byť volanie dec_ref() vnorené do oblasti uzamknutia (samozrejme v tom prípade by sme dec_ref() modifikovali tak, aby sa v nej neuzamykal zámok)? Skúste sa nad tým zamyslieť…
|
1 2 3 4 |
if(r){ kmem.freelist = r->next; inc_ref(r); } |
Vyššie uvedený výsek kódu už patrí do funkcie kalloc(). Po alokovaní novej stránky sa zvýši počet referencií na ňu. Ovšem, je tu jeden chytáčik a problémik. Ak svoj kód upravíte podľa tohto vzoru, po spustení a vyvolaní funkcie kalloc() príde na mieste vykonávania inc_ref() k uviaznutiu (angl. deadlock). Funkciu inc_ref() sme napísali totiž tak, že sa pokúša získať zámok kmem.lock. Ten však už vlastní funkcia kalloc(), preto funkcia inc_ref() musí čakať na uvoľnenie zámku. Ten sa však neuvoľní, pokým neskončí funkcia inc_ref(), pretože až po jej návrate do funkcie kalloc() prichádza k uvoľneniu zámku. Takýto návrh nie je dobrý.
Nakoľko už dopredu vieme, že funkciu inc_ref() budeme potrebovať v tej podobe, v akej je (t. j. so zámkom), musíme nahradiť volanie inc_ref() vo funkcii kalloc() kódom funkcie inc_ref() bez použitia zámkov. Na tento účel môžeme vytvoriť novú funkciu:
|
1 2 3 4 5 |
static void inc_ref_internal(void *pa) { kmem.cntref[PA2IND(pa)]++; } |
A namiesto volania inc_ref() vo funkcii kalloc() použijeme inc_ref_internal(). Pozorný čitateľ si istotne všimol, že funkcia inc_ref_internal() má jediný výkonný riadok kódu. Preto by si nejaký chytrolín povedal, že na jeden riadok kódu predsa nepotrebujeme volať funkciu, a rovno nahradí volanie inc_ref() riadkom kmem.cntref[PA2IND(pa)]++. Áno, fungovalo by to. Ale v reálnom projekte života môže takéto zjednodušenie priniesť trápenie a žiaľ, ak by prišlo k rozširovaniu projektu o novú funkcionalitu. V prípade použitia funkcie stačí zmeniť jej telo, kdežto pri zjednodušenom prístupe bez funkcie je nutné prehľadávať kód, kde všade sa používa pole cntref. Prístup, ktorý používa na obalenie ADT (abstract data type) funkcie, sa pri programovaní bežne využíva, pretože uľahčuje modifikáciu a rozvíjanie kódu.
V prvom rade je potrebné odkomentovať všetky testy v súbore user/cowtest.c (ak sme niektoré zakomentovali). Taktiež je potrebné dať do pôvodného stavu hack použitý pre vývoj prvej časti (na prednáške, v súbore kernel/vm.c viď funkcia uvmunmap())
|
1 2 |
- if(do_free && !(*pte & PTE_COW)){ + if(do_free){ |
Potom prezrieme funkcie uvmcopy() a uvmcow(), a skúsime sa zamyslieť, čo a ako.
Funkcia uvmcopy() je volaná pri systémovom volaní fork(), ktoré duplikuje rodiča. Ak si spomenieme na prednášku, vynorí sa nám v mysli obraz počmáranej tabule, na ktorej sa prednášajúci snažil znázorniť, čo duplikovanie rodičovského virtuálneho adresného priestoru znamená: nealokuje sa žiadna fyzická pamäť (okrem pamäte nutnej na vytvorenie tabuľky stránok v detskom procese); záznamy v tabuľke stránok detského procesu ukazujú na fyzickú pamäť, ktorú používa rodič. Keďže zatiaľ jediným miestom, kde sa zvyšuje počet referencií na stránku, je funkcia kalloc(), a tá sa pri uvmcopy() nevolá, musíme si rozmyslieť, kde do funkcie uvmcopy() dáme volanie inc_ref() tak, aby sme vhodne upravili počet referencií fyzických stránok.
Letmým pohľadom na funkciu uvmcopy() určíme, že najlepšie miesto je pred zavolaním funkcie mappages(). Letmý pohľad však, žiaľ, nestačí. Čo ak volanie mappages() zlyhá? Fyzická stránka, ktorá sa mala mapovať na nejakú virtuálnu adresu (mapovanie zlyhalo) bude mať zvýšený počet referencií, čo nebude v súlade so skutočnosťou (keďže sa mapovanie nepodarilo, tak počet referencií bude o 1 vyšší ako má byť). Treba to urobiť lepšie…
Vo funkcii uvmcow() pred vytvorením nového mapovania (pomocou mappages()) musíme pôvodné mapovanie najprv zrušiť pomocou volania funkcie uvmunmap (na prednáške bolo vysvetlené prečo). Nakoľko sme doteraz nemali implementované počítadlo referencií, tak sme ako posledný argument funkcie uvmunmap() mali hodnotu 0. Ak chceme správne využívať počítadlo refrencií (a uvoľnenie pamäte, ak počet klesne na 0), musíme sa zamyslieť, či a ako zmeniť túto hodnotu.
Po upravení uvmcopy() a uvmcow() je potrebné (podľa zadania) upraviť ešte funkciu copyout:
|
1 2 3 4 5 6 |
pre virtualnu adresu 'dstva' najdi 'pte' ak 'pte' nejestvuje, vrat -1 ak ma 'pte' nastaveny bit PTE_COW: zavolaj uvmcow ak volanie uvmcow zlyhalo: panic |
Kto by nevedel, kam umiestniť tento pseudokód: ešte pred volanie walkaddr().
Nie, nebude!
Prečo?
Z pedagogických dôvodov sme neuviedli všetky kontroly rozsahov adries (napr. vo funkciách uvmcow(), copyout()), ktoré je potrebné implementovať, aby boli všetky testy programu usertests -q úspešné.
Veľa zdaru!
Implementácia prvej časti labu robená na prednáške.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
*** kernel/defs.h *** + int uvmcow(pagetable_t, uint64); *** kernel/riscv.h *** + #define PTE_COW (1L << 8) *** kernel/trap.c *** + } else if(r_scause() == 15){ + if(uvmcow(p->pagetable, r_stval()) < 0){ + p->killed = 1; + } *** user/cowtest.c *** + // TODO TODO TODO iba do implementacie pocitania referencii!!! + //threetest(); + //threetest(); + //threetest(); + //filetest(); *** kernel/vm.c *** uvmunmap() - if(do_free){ + // TODO TODO TODO iba do implementacie pocitania referencii!!! + if(do_free && !(*pte & PTE_COW)){ uvmcopy() + // char *mem; for(i = 0; i < sz; i += PGSIZE){ if((pte = walk(old, i, 0)) == 0) panic("uvmcopy: pte should exist"); if((*pte & PTE_V) == 0) panic("uvmcopy: page not present"); + if (*pte & PTE_W){ + *pte ^= PTE_W; + *pte |= PTE_COW; + } pa = PTE2PA(*pte); flags = PTE_FLAGS(*pte); + /* if((mem = kalloc()) == 0) goto err; memmove(mem, (char*)pa, PGSIZE); if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){ kfree(mem); goto err; } + */ + if(mappages(new, i, PGSIZE, pa, flags) != 0){ + goto err; + } } return 0; + int + uvmcow(pagetable_t pagetable, uint64 va) + { + pte_t *pte; + uint64 pa; + uint flags; + char *mem; + + pte = walk(pagetable, va, 0); + if(pte == 0) + panic("uvmcow: pte should exist"); + if((*pte & PTE_V) == 0) + panic("uvmcow: page not present"); + + if(!(*pte & PTE_COW)){ + printf("uvmcow: PTE_COW not set for 0x%p\n", va); + return -2; + } + + pa = PTE2PA(*pte); + flags = PTE_FLAGS(*pte); + flags ^= PTE_COW; + flags |= PTE_W; + + if((mem = kalloc()) == 0){ + printf("uvmcow: kalloc failed\n"); + return -3; + } + memmove(mem, (char*)pa, PGSIZE); + uvmunmap(pagetable, PGROUNDDOWN(va), 1, 0); + if(mappages(pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, flags) != 0){ + printf("uvmcow: mappages\n"); + kfree(mem); + return -4; + } + + return 0; + } |